// Copyright [2022] <Tianyu Zhu, Shizhen Zhao, Zihang Ren>

#include <algorithm>
#include <cstdlib>  // Header file needed to use srand and rand
#include <iostream>

#include "pulse.h"

Pulse::~Pulse() {
    if (cost_map_) {
        delete[] cost_map_;
        cost_map_ = nullptr;
    }
    if (delay_map_) {
        delete[] delay_map_;
        delay_map_ = nullptr;
    }
    if (visited_) {
        delete[] visited_;
        visited_ = nullptr;
    }
    if (info_) {
        delete[] info_;
        info_ = nullptr;
    }
}

void Pulse::SetupTopology(Graph* graph) {
    graph_ = graph;
    num_nodes_ = graph_->NodeSize();
    cost_map_ = new int[num_nodes_];
    delay_map_ = new int[num_nodes_];
    visited_ = new bool[num_nodes_];
    info_ = new PulseInfo[num_nodes_]();
}

Path Pulse::FindPath(const Flow& flow) {
    // Initialization
    // do dijkstra from end to every other nodes,
    // from two perspectives--cost and delay
    // store the result of dijkstras in cost_map and delay_map
    flow_ = flow;
    clock_t start_time = clock();
    Dijkstra(flow_.to, false, cost_map_);
    Dijkstra(flow_.to, true, delay_map_);
    clock_t end_time = clock();
    std::cout << "Pulse initialization time: "
              << double(end_time - start_time) / CLOCKS_PER_SEC * 1000
              << "(ms).\n";

    // Reset Pulse Algorithm
    int cnt = 0;
    for (int i = 0; i < num_nodes_; ++i) {
        visited_[i] = false;
        info_[i].Clear();
    }
    NodeId start = flow_.from;
    visited_[start] = true;
    total_cost_ = kMaxValue;
    results_.clear();

    // Timer starts
    start_time = clock();
    // Start pulse algorithm
    Path path;
    path.path_info.push_back(start);
    path.cost = 0;
    path.delay = 0;
    num_iterations_ = 0;
    Dfs(start, path);
    // Print time elapse
    end_time = clock();
    std::cout << "Total number of iterations: " << num_iterations_ << "\n";
    std::cout << "Pulse time: "
              << double(end_time - start_time) / CLOCKS_PER_SEC * 1000
              << "(ms).\n";
    return results_.back();
}

// dijkstra algorithm
// if(flag == false)--search according to cost
// if(flag == true)--search according to delay
void Pulse::Dijkstra(NodeId dst_node, bool flag, int* node_to_dst_dis) {
    for (int i = 0; i < num_nodes_; ++i) {
        node_to_dst_dis[i] = kMaxValue;
    }
    node_to_dst_dis[dst_node] = 0;
    std::priority_queue<Node, std::vector<Node>,
                        std::greater<Node>> heap;
    std::vector<bool> visited(num_nodes_, false);
    heap.push(Node(dst_node, 0));
    while (!heap.empty()) {
        NodeId u = heap.top().id;
        int weight_u_to_dst = heap.top().distance;
        heap.pop();
        if (visited[u]) continue;
        visited[u] = true;
        for (Link* link : graph_->GetIngressLinks(u)) {
            NodeId v = link->source_id;
            if (visited[v]) continue;
            int weight = flag ? link->delay : link->cost;
            if (node_to_dst_dis[v] > weight_u_to_dst + weight) {
                node_to_dst_dis[v] = weight_u_to_dst + weight;
                heap.push(Node(v, node_to_dst_dis[v]));
            }
        }
    }
}

// prune accordding to bound and infeasibility
bool Pulse::check(NodeId u, int cost, int delay) {
    if (cost_map_[u] + cost >= total_cost_)
        return false;
    if (delay_map_[u] + delay > flow_.delay_ub)
        return false;
    return true;
}

// update the path node U records
// according to the rule mentioned in Chapter 4 of 2012.10 paper
bool Pulse::update(NodeId u, const Path& path, double p) {
    // Update the path with minimum cost
    if (info_[u].min_cost_path.cost > path.cost) {
        info_[u].min_cost_path = path;
        return true;
    }
    if (info_[u].min_cost_path.delay <= path.delay) {
        return false;
    }
    // Update the path with minimum delay
    if (info_[u].min_delay_path.delay > path.delay) {
        info_[u].min_delay_path = path;
        return true;
    }
    if (info_[u].min_delay_path.cost <= path.cost) {
        return false;
    }
    // if not meet the requirements above,
    // update the random replace path
    if ((info_[u].random_rep_path.delay <= path.delay) &&
        (info_[u].random_rep_path.cost <= path.cost)) {
        return false;
    }
    if (p > 0.5) {
        info_[u].random_rep_path = path;
    }
    return true;
}

// dfs from start to end, use recursion
void Pulse::Dfs(NodeId u, Path& path) {
    ++num_iterations_;
    if (u == flow_.to) {
        if (path.delay > flow_.delay_ub || path.delay < flow_.delay_lb) {
            return;
        }
        if (path.cost > total_cost_) {
            return;
        }
        // total_cost_ = cost * 0.8;
        total_cost_ = path.cost;
        results_.push_back(path);
        return;
    }
    // prune
    if (!check(u, path.cost, path.delay)) {
        return;
    }
    double p = static_cast<double>(rand() % 100) / 100;
    // Use dominance check to prune branches only if there
    // is no delay lower bound.
    if (flow_.delay_lb <= 0 && !update(u, path, p)) {
        return;
    }
    for (Link* link : graph_->GetEgressLinks(u)) {
        NodeId ter = link->ter_id;
        if (visited_[ter]) {
            continue;
        }
        visited_[ter] = true;
        path.cost += link->cost;
        path.delay += link->delay;
        path.path_info.push_back(ter);
        Dfs(ter, path);
        path.cost -= link->cost;
        path.delay -= link->delay;
        path.path_info.pop_back();
        visited_[ter] = false;
    }
}

void Pulse::print() const {
    std::vector<Path> buf;
    for (int i = 0; i < results_.size(); ++i) {
        if (results_[i].delay >= flow_.delay_lb &&
            results_[i].delay <= flow_.delay_ub) {
            buf.push_back(results_[i]);
        }
    }
    results_.back().Print();
}
